package ljl.alg.wangzheng_camp.round1.array_and_list;

import commons.ListNode;

public class _19_remove_last_nth {
    
    /**
     * 这不就是求倒数第 k 个节点
     *
     * 我透，秒过，666
     *
     * */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode d = new ListNode(0, head);
        ListNode pre = d, fast = head;
        while (fast != null && n-- > 0) {
            fast = fast.next;
        }
        while (fast != null) {
            fast = fast.next;
            pre = pre.next;
        }
        pre.next = pre.next.next;
        return d.next;
    }
    
    /*
     * 其它解法：
     *   求长度，再处理，这个对于没刷过题的人来说最直观
     *   用栈，构建虚拟头结点，全 push 进去，pop n 次
     *     最后栈 peek 获取到 pre，利用 pre 删除之
     *
     * 不写了，感觉不是很难
     * */
}
